package com.le.medium.class1;

import org.junit.Test;

/**
 * 给定一个非负整数n，代表二叉树的节点个数。返回能形成多少种不同的二叉树结构
 */
public class Problem06_UniqueBST {

    public static int process(int n) {
        if (n < 0) {
            return 0;
        }
        if (n == 0 || n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            int left = process(i);
            int right = process(n - i - 1);
            res += left * right;
        }
        return res;
    }

    public static int numTrees(int n) {
        if (n < 2) {
            return 1;
        }
        // dp[i]表示当节点个数为i的时候，能组成多少种不同的二叉树结构
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i < n + 1; i++) { // 总结点个数
            for (int j = 1; j < i + 1; j++) { // 左子树结点个数
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }

    @Test
    public void test() {
        System.out.println("hello");
        for (int i = 0; i < 100; i++) {
           if (process(i) != numTrees(i)){
               System.out.println("no:" + i);
               break;
           }
        }
    }
}
